// match regex 

#include "regex.h"
#include "regex_p.h"

static int match_regexlist(char* pcStr, struct regex_list_t* pstRegexList, char** ppcMatchEnd);
static int match_tree(char* pcStr, struct regex_group_t* pstRegex, char** ppcMatchEnd);

static void reset_referinfo()
{
    g_iReferNo = -1;
    memset(&g_stReferInfos, 0, sizeof(g_stReferInfos));
} 

static void set_referinfo(int iReferNo, char* pcStart, char* pcEnd)
{
    g_stReferInfos.astReferInfo[iReferNo].pcStart = pcStart;
    g_stReferInfos.astReferInfo[iReferNo].pcEnd = pcEnd;
} 

static int match_regexlist(char* pcStr, struct regex_list_t* pstRegexList, char** ppcMatchEnd)
{
    char* pcMatchEnd = NULL;
    int iI = 0;
    int iMatchMax = 0;
    int iMatchOver = 0;
    struct regex_list_t* pstNextRegexList;

    if (pstRegexList == NULL)    
    {
        *ppcMatchEnd = pcStr;
        return MATCH_YES;
    } 

    for (iI = 0; iI < pstRegexList->stRegex.iMin; iI++)
    {
        if (pstRegexList->stRegex.acStr[(unsigned char)(*pcStr++)] != 1)
        {
            return MATCH_NO;
        } 
    } 

    iI = 0;
    if (pstRegexList->stRegex.iMax == 0)
    {
        while (pcStr[iMatchMax++])
            ;
    } 
    else
    {
        iMatchMax = pstRegexList->stRegex.iMax; 
    } 

    iMatchOver = iMatchMax - pstRegexList->stRegex.iMin;
    for (pcMatchEnd = pcStr; 
         pstRegexList->stRegex.acStr[(unsigned char)(*pcMatchEnd)] && 
         iI < iMatchOver;
         pcMatchEnd++, iI++)
        ;
    
    pstNextRegexList = pstRegexList->pstNext;
    do 
    {
        if (match_regexlist(pcMatchEnd, pstNextRegexList, ppcMatchEnd))
        {
            return MATCH_YES;
        } 
    } while (pcMatchEnd-- > pcStr);

    return MATCH_NO;
} 

static int make_regexlist(struct regex_group_t* pstRegex)
{
    char* pcCur = NULL;
    struct regex_list_t* pstRegexList = NULL;
    struct regex_list_t* pstCur = NULL;
    struct regex_list_t* pstHead = NULL;

    pcCur = g_stReferInfos.astReferInfo[pstRegex->iReferBackNo].pcStart;
    while (pcCur < g_stReferInfos.astReferInfo[pstRegex->iReferBackNo].pcEnd)
    {
        pstRegexList = malloc(sizeof(*pstRegexList));
        if (pstRegexList == NULL)
        {
            g_errorno = 19;
            return -1;
        } 
        memset(pstRegexList, 0, sizeof(*pstRegexList));

        pstRegexList->stRegex.acStr[(int)*pcCur] = TRUE;
        pstRegexList->stRegex.iMax = pstRegexList->stRegex.iMin = 1;

        pcCur++;

        if (pstHead == NULL)
        {
            pstHead = pstCur = pstRegexList;
        } 
        else
        {
            pstCur->pstNext = pstRegexList;
            pstCur = pstRegexList;
        } 
    } 

    pstRegex->pstRegList = pstHead;
    pstRegex->iMax = pstRegex->iMin = 1;

    return 0;
} 

static int match_tree(char* pcStr, struct regex_group_t* pstRegex, char** ppcMatchEnd)
{
    int iMatch = 0;
    int i = 0;
    char* pcMatchEnd = NULL;
    char* pcMatchStart = NULL;
    char* pcMatchEndMin = pcStr;

    if (pstRegex == NULL) 
    {
        return MATCH_YES;
    } 

    pcMatchStart = pcStr;

    if (pstRegex->iReferBackNo > 0 && pstRegex->pstRegList == NULL)
    {
        make_regexlist(pstRegex);
    } 
    // last leaf
    iMatch = match_regexlist(pcStr, pstRegex->pstRegList, &pcMatchEnd);
    if (iMatch != MATCH_YES)
    {
        return iMatch;
    } 

    for (i = 0; i < pstRegex->iMin; i++)
    {
        iMatch = match_tree(pcMatchEnd, pstRegex->pstChild, &pcMatchEnd);
        if (iMatch != MATCH_YES)
        {
            break;
        } 
    } 

    if (pstRegex->cOr != TRUE)
    {
        if (iMatch != MATCH_YES)
        {
            return iMatch;
        } 
        pcMatchEndMin = pcMatchEnd;

        // match max
        // * +
        if (pstRegex->pstChild != NULL)
        {
            if (pstRegex->iMax == 0) 
            {
                while ((iMatch = match_tree(pcMatchEnd, pstRegex->pstChild, &pcMatchEnd)) == MATCH_YES)
                    ;
            } 
            else
            {
                for (i = 0; i < pstRegex->iMax - pstRegex->iMin; i++)
                {
                    iMatch = match_tree(pcMatchEnd, pstRegex->pstChild, &pcMatchEnd);
                    if (iMatch != MATCH_YES)
                    {
                        break;
                    } 
                } 
            } 
        } 

        *ppcMatchEnd = pcMatchEnd;
        do 
        {
            if (match_tree(pcMatchEnd, pstRegex->pstBrother, ppcMatchEnd))
            {
                set_referinfo(pstRegex->iReferNo, pcMatchStart, *ppcMatchEnd);
                return MATCH_YES;
            } 
        } while (pcMatchEnd-- > pcMatchEndMin);
    } 
    else
    {
        if (iMatch == MATCH_YES)
        {
            *ppcMatchEnd = pcMatchEnd;
            set_referinfo(pstRegex->iReferNo, pcMatchStart, *ppcMatchEnd);

            return iMatch;
        } 
        iMatch = match_tree(pcStr, pstRegex->pstBrother, ppcMatchEnd);
        if (iMatch == MATCH_YES)
        {
            set_referinfo(pstRegex->iReferNo, pcMatchStart, *ppcMatchEnd);
        } 
        return iMatch;
    } 

    return MATCH_NO;
} 

int match_all(char* pcStr, struct regex_all_t* pstRegexAll)
{
    int iMatch = 0;
    char* pcMatchEnd = NULL;

    reset_referinfo();
    if (g_stReferInfos.pcStr == NULL)
        g_stReferInfos.pcStr = pcStr;

    if ((iMatch = match_tree(pcStr, pstRegexAll->pstRegex, &pcMatchEnd)) == MATCH_YES) 
    {
        if (pcMatchEnd == pcStr)
            pcMatchEnd++;
        if (pcMatchEnd > pcStr)
        {
            printf("<%.*s>", (int)(pcMatchEnd - pcStr), pcStr);
        } 
    } 
    else
    {
        printf("%c", *pcStr);
        pcMatchEnd = pcStr + 1;
    } 

    if (pstRegexAll->cHead == TRUE)
    {
        printf("%s", pcMatchEnd);
        return iMatch;
    } 
    else
    {
        // Recursion end condition
        if (pcMatchEnd < pcStr + strlen(pcStr))
        {
            return match_all(pcMatchEnd, pstRegexAll);
        } 
        else
        {
            return iMatch;
        } 
    }
} 

void free_regex(struct regex_group_t* pstRegex)
{
    struct regex_list_t* pstRegexList;
    struct regex_list_t* pstNext;

    if (pstRegex == NULL)
    {
        return;
    } 

    free_regex(pstRegex->pstChild);
    free_regex(pstRegex->pstBrother);

    pstRegexList = pstNext = pstRegex->pstRegList;
    while (pstNext)
    {
        pstNext = pstRegexList->pstNext;
        free(pstRegexList);
        pstRegexList = pstNext;
    } 
    
    free(pstRegex);
    return;
} 

// reverse link list
static struct match_info_t* reverse_matchinfo(struct match_info_t* pstMatchInfo)
{
    struct match_info_t* pstCur = NULL;
    struct match_info_t* pstNext = NULL;
    struct match_info_t* pstPrev = NULL;

    for (pstNext = pstMatchInfo; pstNext != NULL; )
    {
        pstCur = pstNext;
        pstNext = pstNext->pstNext;

        pstCur->pstNext = pstPrev;
        pstPrev = pstCur;
    } 

    return pstPrev;
} 

int match(char* pcRegex, char* pcStr, struct match_info_t** ppstMatchInfo)
{
    int iRetMatch = MATCH_NO;
    char* pcRegexWork = NULL;
    struct regex_all_t stRegex;
    char* pcMatchStart = NULL;
    char* pcMatchEnd = NULL;
    int iMatch = MATCH_NO;
    struct match_info_t* pstMatchInfo = NULL;
    struct match_info_t* pstMatchInfoNew = NULL;

    pcRegexWork = malloc(strlen(pcRegex) + 3);
    if (pcRegexWork == NULL)
    {
        g_errorno = 20;
        return -1;
    } 
    memset(pcRegexWork, 0, strlen(pcRegex) + 3);

    *pcRegexWork = BRACKET_LEFT;
    if (pcRegex[0] == MATCH_START)
    {
        stRegex.cHead = TRUE;
        strcat(pcRegexWork, pcRegex+1);
    } 
    else
    {
        strcat(pcRegexWork, pcRegex);
    } 
    *(pcRegexWork+strlen(pcRegexWork)) = BRACKET_RIGHT;

    if (analyse_all(pcRegexWork, &stRegex.pstRegex) == NULL)
    {
        return -1;
    } 
    free(pcRegexWork);

    g_stReferInfos.pcStr = pcStr;
    for (pcMatchStart = pcStr; *pcMatchStart != 0;  )
    {
        reset_referinfo();
        iMatch = match_tree(pcMatchStart, stRegex.pstRegex, &pcMatchEnd);
        if (iMatch == MATCH_YES)
        {
            if (ppstMatchInfo != NULL)
            {
                pstMatchInfoNew = malloc(sizeof(struct match_info_t));
                if (pstMatchInfoNew == NULL)
                {
                    g_errorno = 21;
                    return -1;
                } 
                memset(pstMatchInfoNew, 0, sizeof(*pstMatchInfoNew));
                pstMatchInfoNew->pcMatchStart = pcMatchStart;
                pstMatchInfoNew->pcMatchEnd = pcMatchEnd;

                pstMatchInfoNew->pstNext = pstMatchInfo;
                pstMatchInfo = pstMatchInfoNew;
            } 

            pcMatchStart = pcMatchEnd;            

            iRetMatch = MATCH_YES;
        } 
        else
        {
            pcMatchStart++;
        } 

        if (stRegex.cHead == TRUE)
        {
            break;
        } 
    } 

    free_regex(stRegex.pstRegex);

    if (ppstMatchInfo != NULL)
    {
        *ppstMatchInfo = reverse_matchinfo(pstMatchInfo);
    } 
    return iRetMatch;
} 

int match_str(char* pcRegex, char* pcStr)
{
    return match(pcRegex, pcStr, NULL);
} 

